#
# @lc app=leetcode.cn id=17 lang=python
#
# [17] 电话号码的字母组合
#

# @lc code=start
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        self.dict = {
            '2':['a','b','c'],
            '3':['d','e','f'],
            '4':['g','h','i'],
            '5':['j','k','l'],
            '6':['m','n','o'],
            '7':['p','q','r','s'],
            '8':['t','u','v'],
            '9':['w','x','y','z']
        }
        
        self.digits = digits
        self.result = []
        self.str = ''
        if len(digits) == 0:
            return []
        self.loop(0)
        return self.result

    def loop(self, index):
        if index >= len(self.digits):
            self.result.append(self.str)
            return
        for value in self.dict[self.digits[index]]:
            self.str += value
            self.loop(index+1)
            self.str = self.str[:-1]
        
# @lc code=end

